#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <iostream>

using namespace std;

int findSubstringInWraproundString(string s) {
    int n = s.size();
    vector<int> dp(n + 10, 1);
    
    for (int i = 1; i < n; ++i)
    {
        if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
        {
            dp[i] += dp[i - 1];
        }
    }

    int ret = 0;
    int hash[26] = { 0 };
    for (int i = 0; i < n; ++i)
    {
        hash[s[i] - 'a'] = max(hash[s[i] - 'a'] , dp[i]);
    }

    for (auto& e : hash)
        ret += e;

    return ret;
}

int lengthOfLIS(const vector<int>& nums) {
    int n = nums.size();

    vector<int> dp(n + 10, 1);
    dp[0] = 0;
    int ret = INT_MIN;
    for (int i = 1; i <= n; ++i)
    {
        int num = INT_MIN;
        for (int j = i - 1; j >= 1; --j)
        {
            if (nums[j - 1] < nums[i - 1])
            {
                num = max(num, dp[j]);
            }
        }
        if (num != INT_MIN)
            dp[i] += num;
    
        ret = max(ret, dp[i]);
    }


    return ret;
}
int main()
{
    //findSubstringInWraproundString("cac");
    lengthOfLIS({ 1,3,6,7,9,4,10,5,6 });
	return 0;
}